"""
https://leetcode.cn/problems/longest-increasing-subsequence/description/

300. 最长递增子序列
已解答
中等
相关标签
相关企业
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

 
示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1
 

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104
 

进阶：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?
"""

from typing import List


class Solution:
    """
    理解为：维护一个数组，数组元素t[n]表示尾部元素为nums[n]的最长数量
    则所求值必为该数组中的最大元素。

    对于t[n]，当n>=1时有
    if nums[n]>nums[n-1],则t[n]=t[n-1]+1
    else nums[n]=1

    t[0]=1

    以上思路，是基于连续子序列的。如果考虑到子序列允许不连续，则：
    维护一个有序列表，表示以元素n为尾部元素的最长数量。
    对于遍历到的元素n,则找到小于元素n的所有值，找到其中最大的，在此基础上+1。

    能否直接取小于n的最大元素的数量value，并不能，是需要优化的点。
    可用一个list+map的方式实现：list是递增对应count；map则是每个最长数量对应的key
    当遍历一个值时，先判断list中前一个元素及其最长数量。
    1. 如果没有前一个元素，则该值对应最长数量为1。找到map中对应1的值，将对应的元素替换；同时list中也对应的增删；
    2. 如果有前一个元素，则可计算到新的最长数量，假定为m。找到map中对应m的最长数量，有则替换，并在list中对应增删；无则直接在后面追加。

    先考虑不优化的情况。
    此时的效率已经超过70%了，尽管时间复杂度只有O(n^2)

    """
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp=[1]*len(nums)

        for i in range(1,len(nums)):
            max_len=0
            for j in range(i):
                if nums[i]>nums[j]:
                    max_len=max(dp[j],max_len)
            dp[i]=max_len+1

        return max(dp)

if __name__=='__main__':
    nums=[7,7,7,7,7,7,7]

    sol=Solution()
    res=sol.lengthOfLIS(nums)
    print(res)

    pass